package LC;

import java.util.LinkedList;
import java.util.Queue;

class TreeLinkNode {
    int val;
    TreeLinkNode left, right, next;

    TreeLinkNode(int x) {
        val = x;
    }
}

public class LC30 {
    public void connect(TreeLinkNode root) {
        if (root==null) return;
        Queue<TreeLinkNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()){
            int len =queue.size();
            TreeLinkNode t1 =  queue.poll();
            if(t1.left!=null) queue.offer(t1.left);
            if(t1.right!=null) queue.offer(t1.right);
            for (int i = 1; i < len; i++) {
                TreeLinkNode t2 =  queue.poll();
                t1.next = t2;
                t1 = t2;
                if(t1.left!=null) queue.offer(t1.left);
                if(t1.right!=null) queue.offer(t1.right);
            }
            t1.next = null;
        }
    }
}